Data structures frequently contain data elements which are to be differentiated by their positions with respect to each other. Position coding methods make this possible by allocating position codes to all data elements in a predetermined sequence.
A position coding method is described in [1] which is employed in a method for binary coding of XML data. This method uses XML schema definitions (in the context of a standardized MPEG-7 method, for example) in order to generate the codes for the individual data elements of the XML description. In this respect, individual elements or element groups of the same type as defined by the XML schema definition can occur several times in the document. In this case, a position code (PC) is transmitted. The position code includes the binary representation of a whole number which specifies the position with regard to the adjacent elements. The position code is associated with the element on the basis of the position with respect to the adjacent elements in the document to be coded. This has the advantage that the position code of an element is preserved irrespective of the sequence in which adjacent elements are transmitted. Elements, therefore, can be lost in transmission without this affecting the position codes or the position of the elements which are subsequently decoded via a decoder.
A disadvantage of this known method is that the XML document must be known at the time of coding since no new positions can be inserted with the previously existing position coding; instead, new positions can just be appended. This is a disadvantage especially when an XML document is already to be coded or transmitted while it is being created; for example, in live transmissions according to a transmission standard, such as MPEG-4 or MPEG-7.
For the purposes of solving this problem, gaps can be left between the position codes used, which can be filled when needed. Particularly in the case of live coding, however, the need-based readiness of such gaps which must be defined in advance is difficult to predict. Additionally, the overall quantity of possible gaps is limited by the XML schema definition in many cases. Then, if no more position codes kept free by such gaps are available at the position to be inserted, all the adjacent elements already sent have to be transmitted again with newly generated position codes. This frequently occurs in the case of a number of data elements of the same type; for example, in the case of identical elements or element groups occurring several times in a document. The consequence is a marked deterioration in coding efficiency and also a markedly increased processing overhead both at the coder and at the decoder.
The present invention is therefore directed toward a method and a device for coding positions of data elements in a data structure in which the positions of newly added data elements can be coded in a simple and efficient manner.